package cs;

import java.util.Arrays;

/**
 * 检查系统是否处于安全状态
 *
 */
class BankerAlgorithm {

    // 资源的种类数
    private int resourceTypes;

    // 资源总量
    private int[] totalResources;

    // 已分配资源
    private int[][] allocatedResources;

    // 进程对资源的最大需求
    private int[][] maxDemand;

    // 剩余资源
    private int[] availableResources;

    // 初始化银行家算法的数据结构
    public BankerAlgorithm(int resourceTypes, int[] totalResources, int[][] allocatedResources, int[][] maxDemand) {
        this.resourceTypes = resourceTypes;
        this.totalResources = totalResources.clone();
        this.allocatedResources = allocatedResources.clone();
        this.maxDemand = maxDemand.clone();
        availableResources = new int[resourceTypes];
        calculateAvailableResources();
    }

    // 计算剩余资源
    private void calculateAvailableResources() {
        for (int i = 0; i < resourceTypes; i++) {
            int sumAllocated = 0;
            for (int j = 0; j < allocatedResources.length; j++) {
                sumAllocated += allocatedResources[j][i];
            }
            availableResources[i] = totalResources[i] - sumAllocated;
        }
    }



    /**
     * 安全性检测函数
     * @return
     */
    public boolean isSafeState() {
        int[] work = availableResources.clone();
        boolean[] finish = new boolean[allocatedResources.length];
        Arrays.fill(finish, false);

        int count = 0;
        // allocatedResources.length == 5，如果资源满足需求，每轮最少找到1个，5轮足够找出所有满足的进程
        while (count < allocatedResources.length) {
            boolean found = false;
            for (int i = 0; i < allocatedResources.length; i++) {
                // 已经满足的就不需要再检查
                if (!finish[i]) {
                    boolean canFinish = true;
                    for (int j = 0; j < resourceTypes; j++) {
                        if (maxDemand[i][j] - allocatedResources[i][j] > work[j]) {
                            canFinish = false;
                            break;
                        }
                    }
                    if (canFinish) {
                        for (int j = 0; j < resourceTypes; j++) {
                            // 这一步是模拟当前进程释放资源，可以让本来资源不足的进程满足运行条件
                            work[j] += allocatedResources[i][j];
                        }
                        finish[i] = true;
                        found = true;
                        count++;
                    }
                }
            }
            // 5个进程需要的资源没有一个满足要求的，直接退出
            if (!found) {
                return false;
            }
        }
        return true;
    }

    // 资源请求处理函数
    public boolean requestResources(int processId, int[] request) {
        // 检查请求是否合法
        for (int i = 0; i < resourceTypes; i++) {
            if (request[i] > maxDemand[processId][i] - allocatedResources[processId][i] || request[i] > availableResources[i]) {
                return false;
            }
        }

        // 模拟分配资源
        for (int i = 0; i < resourceTypes; i++) {
            availableResources[i] -= request[i];
            allocatedResources[processId][i] += request[i];
        }

        // 检查是否安全
        if (isSafeState()) {
            return true;
        } else {
            // 恢复原来的状态
            for (int i = 0; i < resourceTypes; i++) {
                availableResources[i] += request[i];
                allocatedResources[processId][i] -= request[i];
            }
            return false;
        }
    }

    public static void main(String[] args) {
//        资源共有3种
        int resourceTypes = 3;
        int[] totalResources = {10, 5, 7};
//        每个进程已经分配的资源，每一行就是代表一个进程，这里是有5个进程
        int[][] allocatedResources = {
                {0, 1, 0},
                {2, 0, 0},
                {3, 0, 2},
                {2, 1, 1},
                {0, 0, 2}
        };
        int[][] maxDemand = {
                {7, 5, 3},
                {3, 2, 2},
                {9, 0, 2},
                {2, 2, 2},
                {4, 3, 3}
        };

        BankerAlgorithm banker = new BankerAlgorithm(resourceTypes, totalResources, allocatedResources, maxDemand);

        int processId = 1;
        int[] request = {1, 0, 2};

        if (banker.requestResources(processId, request)) {
            System.out.println("资源请求成功，系统处于安全状态");
        } else {
            System.out.println("资源请求失败，系统处于不安全状态");
        }
    }
}
